/*
一个无序数组里面只有一个数重复奇数次,
其它数都重复偶数次, 
请写个算法找出是哪个数重复了奇数次.
老兄先给出个 O(n2) 的,
在提示下, 排序,然后遍历,
问复杂度多少, 
算了半天没弄出来.
*/

#include "junix.h"
using namespace std;

// if 0 is odd ????????
uint64_t f(uint64_t v[], uint64_t  size) {
	uint64_t txor = 0;
	for (uint64_t i=0;i<size;i++) 
		txor = txor^v[i];

	for (uint64_t i=0;i<size;i++) 
		if ( !(txor^v[i]) )
			return v[i];

	assert(true);
	return 0;
}

int main(int argc, char **argv)
{
	uint64_t v[]={1,1,2,2,3,2,3};
	std::cout<<f(v,sizeof(v)/sizeof(v[0]))<<std::endl;
}
